package com.mdnote.practice.binary_tree;

import java.util.LinkedList;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/14 0014
 * @description 序列化和反序列化二叉搜索树
 */
public class LeetCode449 {


    public static void main(String[] args) {
        LeetCode449 leetCode449 = new LeetCode449();

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(6);
        String source = leetCode449.serialize(root);
        System.out.println(source);

        TreeNode deserialize = leetCode449.deserialize(source);

        System.out.println(deserialize);
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder stringBuilder = new StringBuilder();
        _serialize(root, stringBuilder);

        return stringBuilder.toString();
    }

    private void _serialize(TreeNode node, StringBuilder stringBuilder) {

        if (node == null) {
            return;
        }

        _serialize(node.left, stringBuilder);
        _serialize(node.right, stringBuilder);

        stringBuilder.append(node.val).append(" ");
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }

        LinkedList<Integer> queue = new LinkedList<>();
        String[] strs = data.split("\\s+");
        for (String str : strs) {
            queue.offer(Integer.valueOf(str));
        }

        return _deserialize(queue, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }

    private TreeNode _deserialize(LinkedList<Integer> queue, int maxVal, int minVal) {
        Integer last = queue.peekLast();
        if (last == null || last > maxVal || last < minVal) {
            return null;
        }
        last = queue.removeLast();
        TreeNode node = new TreeNode(last);
        node.right = _deserialize(queue, maxVal, last);
        node.left = _deserialize(queue, last, minVal);

        return node;

    }

    public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }
}
